package com.zwj.interview.单调栈;

import java.util.Arrays;
import java.util.Stack;

/**
 * 输入一个数组，它的每个数字是某天的温度。请计算每天需要等几天才会出现更高的温度。
 * 例如，如果输入数组[35，31，33，36，34]，那么输出为[3，1，1，0，0]。
 * 由于第1天的温度是35℃，要等3天才会出现更高的温度36℃，因此对应的输出为3。第4天的温度是36℃，后面没有更高的温度，它对应的输出是0。其他的以此类推
 * <p>
 * 动画演示：https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/
 */
public class 每日温度 {

    /**
     * @param T
     * @return 始终保证栈底的元素是大的
     * 和下一个表达的数几乎一样
     */
   static  int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 这里放元素索引，而不是元素
        Stack<Integer> s = new Stack<>();
        /* 单调栈模板 */  //还是从后面开始遍历
        for (int i = n - 1; i >= 0; i--) {
            while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
                s.pop();
            }
            // 得到索引间距
            res[i] = s.isEmpty() ? 0 : (s.peek() - i);
            // 将索引入栈，而不是元素
            s.push(i);
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{35, 31, 33, 36, 34})));
    }









}
